A New Law to Describe Quantum Computing’s Rise?

In December 2018, scientists at Google AI ran a calculation on Google’s best quantum processor. They were able to reproduce the computation using a regular laptop. Then in January, they ran the same test on an improved version of the quantum chip. This time they had to use a powerful desktop computer to simulate the result. By February, there were no longer any classical computers in the building that could simulate their quantum counterparts. The researchers had to request time on Google’s enormous server network to do that.

“Somewhere in February I had to make calls to say, ‘Hey, we need more quota,’” said Hartmut Neven, the director of the Quantum Artificial Intelligence lab. “We were running jobs comprised of a million processors.”

That rapid improvement has led to what’s being called “Neven’s law,” a new kind of rule to describe how quickly quantum computers are gaining on classical ones. The rule began as an in-house observation before Neven mentioned it in May at the Google Quantum Spring Symposium. There, he said that quantum computers are gaining computational power relative to classical ones at a “doubly exponential” rate — a staggeringly fast clip.

With double exponential growth, “it looks like nothing is happening, nothing is happening, and then whoops, suddenly you’re in a different world,” Neven said. “That’s what we’re experiencing here.”

Even exponential growth is pretty fast. It means that some quantity grows by powers of 2: 2¹, 2², 2³, 2⁴. The first few increases might not be that noticeable, but subsequent jumps are massive. Moore’s law, the famous guideline stating (roughly) that computing power doubles every two years, is exponential.

Doubly exponential growth is far more dramatic. Instead of increasing by powers of 2, quantities grow by powers of powers of 2: $latex 2^{2^1}, 2^{2^2}, 2^{2^3}, 2^{2^4}$. Doubly exponential growth featured in the recent Quanta story “Computer Scientists Expand the Frontiers of Verifiable Knowledge,” where it described the extreme rate at which certain computational problems increase in complexity. Doubly exponential growth is so singular that it’s hard to find examples of it in the real world. The rate of progress in quantum computing may be the first.

The doubly exponential rate at which, according to Neven, quantum computers are gaining on classical ones is a result of two exponential factors combined with each other. The first is that quantum computers have an intrinsic exponential advantage over classical ones: If a quantum circuit has four quantum bits, for example, it takes a classical circuit with 16 ordinary bits to achieve equivalent computational power. This would be true even if quantum technology never improved.

The second exponential factor comes from the rapid improvement of quantum processors. Neven says that Google’s best quantum chips have recently been improving at an exponential rate. (This rapid improvement has been driven by a reduction in the error rate in the quantum circuits. Reducing the error rate has allowed the engineers to build larger quantum processors, Neven said.) If classical computers require exponentially more computational power to simulate quantum processors, and those quantum processors are growing exponentially more powerful with time, you end up with this doubly exponential relationship between quantum and classical machines.

Not everyone is convinced by this. For one thing, classical computers are not standing still. Ordinary computer chips continue to improve, even if Moore’s law may be ending. In addition, computer scientists constantly devise more efficient algorithms that help classical computers keep pace.

“When looking at all the moving parts, including improvements on the classical and quantum sides, it’s hard for me to say it’s doubly exponential,” said Andrew Childs, the co-director of the Joint Center for Quantum Information and Computer Science at the University of Maryland.

While the exact rate at which quantum computers are closing in on classical ones might be debatable, there’s no doubt quantum technology is improving, and fast.

“I think the undeniable reality of this progress puts the ball firmly in the court of those who believe scalable quantum computing can’t work,” wrote Scott Aaronson, a computer scientist at the University of Texas, Austin, in an email. “They’re the ones who need to articulate where and why the progress will stop.”

A paramount goal in the field of quantum computing is to perform an efficient quantum calculation that cannot be simulated in any reasonable amount of time on even the most powerful classical computer (currently the Summit supercomputer at Oak Ridge National Laboratory). Among the different research groups developing quantum computers, Google has been particularly vocal about its pursuit of this milestone, known as “quantum supremacy.”

So far, quantum supremacy has proved elusive — sometimes seemingly around the corner, but never yet at hand. But if Neven’s law holds, it can’t be far away. Neven wouldn’t say exactly when he anticipates the Google team will achieve quantum supremacy, but he allowed that it could happen soon.

“We often say we think we will achieve it in 2019,” Neven said. “The writing is on the wall.”

This article was reprinted in ScientificAmerican.com.